package cn.myworld.algorithm.opt;

/**
 * 快慢指针_有环链表入口问题
 */
public class CircleListIn {

    public static void main(String[] args) {

        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
        Node<String> seven = new Node<String>("gg", null);

        // 节点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;

        // 产生环
        seven.next = third;

        // 查找环的入口节点
        // 当快慢指针相遇时，我们可以判断到链表中有环，这是重新设定一个指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口，数学证明略
        Node<String> entrance = getEntrance(first);
        System.out.println("first链表中环的入口节点元素为：" + entrance.data);
    }

    /**
     * 查找有环链表中的入口节点
     * @param first 链表首节点
     * @return 环的入口节点
     */
    public static Node<String> getEntrance(Node<String> first) {
        // 定义快慢指针
        Node<String> fast = first;
        Node<String> slow = first;
        Node<String> temp = null;
        // 遍历链表，先找到环（快慢指针相遇），准备一个临时指针，指向链表的首节点，继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的节点就是环的入口
        while (fast != null && fast.next != null) {
            // 变换快慢指针
            fast = fast.next.next;
            slow = slow.next;
            // 判断快慢指针是否相遇
            if (fast.equals(slow)) {
                temp = first;
                continue;
            }
            // 让临时节点变换
            if (temp != null) {
                temp = temp.next;
                // 判断临时指针是否和慢指针相遇
                if (temp.equals(slow)) {
                    break;
                }
            }
        }

        return temp;
    }

    /**
     * 节点类
     */
    private static class Node<T> {
        T data;
        Node<T> next;
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }

    }

}
